class Solution {
    // 最朴素的二分查找算法
    public int search(int[] nums, int t) {
        int left = 0;
        int right = nums.length-1;
        while (left <= right) {
            int mid = (left+right) / 2; // 这里可能会有溢出的风险
            // mid = left + (right-left) / 2; // 可以写成这样
            if (nums[mid] > t) {
                right = mid-1;
            } else if (nums[mid] < t) {
                left = mid+1;
            } else {
                return mid;
            }
        }
        return -1;
    }


    // 最普通的二分查找算法（未优化）
    public static int[] searchRange(int[] nums, int target) {
        int[] ans = {-1, -1};
        if (nums.length == 0) {
            return ans;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                // 一直遍历到边界为止
                int i = mid - 1;
                int j = mid + 1;
                while (nums[i] == target) { // 左边界
                    i--;
                }
                while (nums[j] == target) { // 右边界
                    j++;
                }
                ans[0] = i + 1;
                ans[1] = j - 1;
                break;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {5,7,7,8,8,10};
        searchRange(nums, 8);
    }







}